import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 09 - 05
 * Time: 19:53
 */
//牛客 三数之和
public class Solution5 {
    //官方推荐方法
    public static ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        ArrayList<ArrayList<Integer>> arrayList1 = new ArrayList<>();
        if (num.length < 3) return arrayList1;
        Arrays.sort(num);
        int i = 0;
        while (i < num.length - 2) {
            if(i != 0 && num[i] == num[i - 1]) {//去重，注意是num[i]==num[i-1]
                i++;
                continue;
            }
            int left = i + 1;
            int right = num.length - 1;
            while(left < right) {
                if(num[left] + num[right] == -num[i]) {
                    ArrayList<Integer> arrayList2 = new ArrayList<>();
                    arrayList2.add(num[i]);
                    arrayList2.add(num[left]);
                    arrayList2.add(num[right]);
                    arrayList1.add(arrayList2);
                    while(left + 1 < right && num[left] == num[left + 1]) {//去重，要用while循环，不要用if语句。while循环其中一个条件是left+1<right
                        left++;
                    }
                    while(left < right - 1 && num[right] == num[right - 1]) {//去重，要用while循环，不要用if语句。while循环其中一个条件是left<right-1
                        right--;
                    }
                    left++;
                    right--;
                } else if (num[left] + num[right] > -num[i]) {
                    right--;
                } else if (num[left] + num[right] < -num[i]) {
                    left++;
                }
            }
            i++;
        }
        return arrayList1;
    }
}
